package leetcode.code0677;

import java.util.HashMap;
import java.util.Map;

public class MapSum1 {

	class Node {
		private Node[] c;
		private int sum;

		public Node() {
			c = new Node[26];
		}

		public void add(int num) {
			sum += num;
		}

		public void sub(int num) {
			sum -= num;
		}

		public Node subChar(char c, int num) {
			int cindex = c - 'a';
			Node cNode = this.c[cindex];
			cNode.sub(num);
			return cNode;
		}

		public Node addChar(char c, int num) {
			int cindex = c - 'a';
			Node cNode = this.c[cindex];
			if (cNode == null) {
				cNode = new Node();
				this.c[cindex] = cNode;
			}
			cNode.add(num);
			return cNode;
		}

		public int getSum() {
			return this.sum;
		}

		public Node next(char c) {
			int cindex = c - 'a';
			return this.c[cindex];
		}
	}

	Node root;

	private Map<String, Integer> exist;

	public MapSum1() {
		root = new Node();
		exist = new HashMap<>();
	}

	public void insert(String key, int val) {
		Node node = root;
		char[] chars = key.toCharArray();
		int diff = val;
		if (this.exist.containsKey(key)) {
			diff = val - this.exist.get(key);
		}
		if (diff != 0) {
			for (char c : chars) {
				node = node.addChar(c, diff);// 添加字符并累加前缀
			}
			this.exist.put(key, val);
		}
	}

	public int sum(String prefix) {
		Node node = root;
		char[] chars = prefix.toCharArray();
		int idx = 0;
		while (node != null && idx < chars.length) {
			node = node.next(chars[idx++]);
		}
		return node == null ? 0 : node.getSum();// node的累加和
	}

	public static void main(String[] args) {
		MapSum1 mapSum = new MapSum1();
		mapSum.insert("apple", 3);
		int a = mapSum.sum("ap"); // return 3 (apple = 3)
		mapSum.insert("app", 2);
		mapSum.insert("apple", 2);
		int b = mapSum.sum("a"); // return 5 (apple + app = 3 + 2 = 5)
		System.out.println(a == 3);
		System.out.println(a);
		System.out.println(b == 4);
		System.out.println(b);
	}

	private void test1() {
		MapSum1 mapSum = new MapSum1();
		mapSum.insert("a", 3);
		int a = mapSum.sum("ap"); // return 3 (apple = 3)
		mapSum.insert("b", 2);
		int b = mapSum.sum("a"); // return 5 (apple + app = 3 + 2 = 5)
		System.out.println(a == 0);
		System.out.println(b == 3);
	}

	private void test() {
		MapSum1 mapSum = new MapSum1();
		mapSum.insert("apple", 3);
		int a = mapSum.sum("ap"); // return 3 (apple = 3)
		mapSum.insert("app", 2);
		int b = mapSum.sum("ap"); // return 5 (apple + app = 3 + 2 = 5)
		System.out.println(a == 3);
		System.out.println(b == 5);
	}

}
